package algorithm.kmp;

import java.util.Arrays;

/**
 * KMP算法
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-06
 */
public class KMPAlgorithm {

    public static void main(String[] args) {

        String str = "BBC ABCDAB ABCDABCDABDE";
        String subStr = "ABCDABD";
        int[] next = kmpNext(subStr);
        int index = kmpSearch(str, subStr, next);
        System.out.println(Arrays.toString(next));
        System.out.println("index : " + index);
    }

    /**
     * KMP查找
     *
     * @param str    源字符串
     * @param subStr 字串
     * @param next   部分匹配值表
     * @return 字串在源字符串中的索引
     */
    private static int kmpSearch(String str, String subStr, int[] next) {
        for (int i = 0, j = 0; i < str.length(); i++) {
            // 跳过部分
            while (j > 0 && str.charAt(i) != subStr.charAt(j)) {
                j = next[j - 1];
            }
            // 相同的时候 j++
            if (str.charAt(i) == subStr.charAt(j)) {
                j++;
            }
            // 说明此时已经找到了 此时上面 j++了 但i还没有++ 所有 要+1
            if (j == subStr.length()) {
                return i - j + 1;
            }
        }
        // 循环完还没找到返回 -1
        return -1;
    }

    /**
     * 获取一个字符串的部分匹配值表 一般是字串
     *
     * @param str 字串
     * @return 部分匹配值
     */
    public static int[] kmpNext(String str) {
        int[] next = new int[str.length()];
        // 一个字符的时候  前缀和后缀肯定不会有相同的
        next[0] = 0;
        for (int i = 1, j = 0; i < str.length(); i++) {
            // 前面和后面不相同时候  需要找到 j 此时j就是字符串不相同的地方
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }
            // 前面和后面相同时候 匹配值就+1
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
